package com.jack.leetcode.eachproblem_2020;

import java.util.ArrayList;
import java.util.List;

public class 解数独 {

    public static void main(String[] args) {
        System.out.println((8/3*3 + 8/3));
    }

    public void solveSudoku(char[][] board) {
        boolean[][] squares = new boolean[9][9];
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        List<int[]> spaces = new ArrayList<int[]>();

        for(int i = 0;i < 9;i++){
            for(int j = 0;j < 9;j++){
                if(board[i][j] == '.'){
                    spaces.add(new int[]{i,j});
                    continue;
                }
                squares[i/3*3 + j/3][board[i][j] - '1'] = rows[i][board[i][j] - '1'] = cols[j][board[i][j] - '1'] = true;
            }
        }
        dfs(board, 0, squares, rows, cols, spaces);
    }

    private boolean isValid = false;
    private void dfs(char[][] board, int cnt, boolean[][] squares,
                     boolean[][] rows, boolean[][] cols, List<int[]> spaces){
        if(cnt == spaces.size()){
            isValid = true;
            return;
        }
        int[] space = spaces.get(cnt);
        int i = space[0], j = space[1];
        for(int digit = 0;digit < 9 && !isValid;digit++){
            if(!squares[i/3*3 + j/3][digit] &&
                    !rows[i][digit] && !cols[j][digit]){
                squares[i/3*3 + j/3][digit] = rows[i][digit] = cols[j][digit] = true;
                board[i][j] = (char) (digit + '0' + 1);
                dfs(board, cnt+1, squares, rows, cols, spaces);
                squares[i/3*3 + j/3][digit] = rows[i][digit] = cols[j][digit] = false;
            }
        }
    }
}
